\chapter {Experimental results}\label{results}
\markboth {Chapter \ref{results}. Experimental results}{}

\begin{flushright}
\sl
If one finds a difficulty in a calculation which is otherwise quite convincing, one should not push the difficulty away; one should rather try to make it the centre of the whole thing.
\end{flushright}

\begin{flushright}
\sl
Werner Heisenberg
\end{flushright}
\par\vfill\par

In this chapter, the methodology, intended as the collection of the high-level synthesis flow and the genetic algorithm used for design space exploration, is validated through the simulation on a set of benchmarks. In Section~\ref{results:implementation} the development framework is presented. The following Sections reports some simulation results. In Section~\ref{results:evaluations} the estimations of the area model, proposed in the Section~\ref{details:evaluation}, are validated and compared with the real values obtained from effective RTL synthesis synthesis on FPGA device. Then, in Section~\ref{results:dse}, the proposed algorithm for the design space exploration has been applied to some common benchmarks, coming from the lecterature. The results are evaluated and compared with those obtained using the standard high-level synthesis flow. 
At the end, in Section~\ref{results:jpeg} a case study is presented: the implementation on hardware modules of some steps of the JPEG encoder algorithm. This has been presented since it shows how the proposed methodology can be actually applied to real problems.

\section{Development Framework}\label{results:implementation}

The described methodology has been implemented in a C++ High-Level Synthesis framework and it has been integrated into the PandA \cite{panda} environment (an open-source 
framework covering different aspects of the hardware-software design of embedded 
systems). 

Evolutionary computation has been provided using Open BEAGLE framework~\cite{openbeagle}. Open BEAGLE provides an high-level software environment to perform a large set of evolutionary computations, with support for different genetic algorithms and encoding features. 

The RTL synthesis of the high-level synthesis benchmarks has been performed using the Xilinx ISE ver.~8.1i on a Virtex II-PRO XC2VP30 FPGA device. The case study presented in Section~\ref{results:jpeg} has been synthetized on a Virtex II-PRO XC2VP4 FPGA device, since the number of configurable logic blocks on this device (6,768 logic cells) is smaller than the Xilinx XC2VP30 FPGA device (30,816 logic cells). The result is a stricter area constraint that shows how the design space exploration algorithm can be exploited to find suitable solutions.

\section{High-Level Synthesis Evaluations}\label{results:evaluations}

The high-level synthesis flow proposed in Section~\ref{mixed:flow} has been applied to a set of common high-level synthesis benchmarks (see Table~\ref{tab:benchmarks} for details).

\begin{small}
\begin{table}
\centering
 \caption{\label{tab:benchmarks}Operations and branching blocks for tested benchmarks}
{\small
\begin{tabular}{|l|c|c|}
\hline
\textbf{Benchmark} & \textbf{\#Operations} & \textbf{Branching Blocks}\\
\hline
 Kim       & 32  &  3  \\
 Maha      & 28  &  6  \\
 Shewa     & 27  &  6  \\
\hline
 Arf       & 30  &  1  \\
 Dct       & 50  &  1  \\
 Dct\_Wang & 49  &  1 \\
 Dist      & 54  &  1 \\
 Pr1       & 43  &  1  \\
 Pr2       & 50  &  1  \\
 Wdf       & 39  &  1  \\
\hline
\end{tabular}
}
\end{table}
\end{small}

\subsubsection{Behavioral validation}

Since Verilog language~\cite{Verilog} allows the interaction with source code in a C language, a regression test has been implemented to validate the behavior of the implemented designs. In the simple automated test framework created, random values have been generated and presented at the input of the module coming from the high-level synthesis flow. The same inputs are used to launch the behavioral specification function that had been parsed at the beginning of the flow~(see section~\ref{details:gimple}). The results coming from both executions are compared. Since the simulated module is the structural representation of the specification written in C language, the behaviors have to be the identical. The final comparison tests if some implementation has a different behavior from the specification that it originated from. The simulations performed revealed that all the final designs produced respect the behavioral specification.

\subsubsection{Area model validation}

To validate the area model presented in Section~\ref{details:evaluation}, the designs coming out from the high-level synthesis flow have been synthetised on real FPGA devices and results coming from the synthesis are compared with estimations made with the model, as shown in Table~\ref{tab:modelvalidation}. Figure~\ref{figure:modelValidation} shows the error between the area model estimation and the real synthesis results as the size of the resulting design increases.

The comparison shows an average error about 4.0\% (with a standard deviance about 2.8\%). The maximum error is less than 10\%. These values demostrate that the model can be considered as a quite good estimator for the real area occupied by the final design. So its use as fitness function is justified, since it is able to give a good estimation (although with some noise) of the area that the design solution, created starting from the informations encoded into the individual (as described in the section~\ref{details:fitness}), will effectively occupy.

\begin{figure}
  \centering
  \includegraphics[width=0.78\columnwidth]{./chapters/experimental_results/images/modelValidation.jpg}
  \caption{Validation of the FPGA area model}\label{figure:modelValidation}
\end{figure}

\begin{small}
\begin{table}
\centering
 \caption{\label{tab:modelvalidation} Comparison between area model estimations and Xilinx tool synthesis results, on a Virtex II-PRO XC2VP30 FPGA device}
{\small
\begin{tabular}{|l|r|r|r|}
\hline
\textbf{Benchmark} & \textbf{Area Model} & \textbf{Xilinx synthesis} & \textbf{Absolute error} \\
 & \textbf{(in CLBs)}  & \textbf{   (in CLBs)}& \textbf{   (in \%)}\\
\hline
 Kim      & 1215  & 1245  & 2.41  \\
 Maha     & 1116  & 1089  & 2.48 \\
 Shewa    & 1156  & 1057  & 9.37 \\
 Arf      & 5462  & 5376  & 1.60	\\
 Dct      & 7384  & 6974  & 5.88 \\
 Dct\_Wang & 6709  & 6665  & 0.66 \\
 Dist     & 14311 & 13283 & 7.74 \\
 Pr1      & 5527  & 5396  & 2.43 \\
 Pr2      & 9662  & 9122  & 5.92 \\
 Wdf      & 2833  & 2883  & 1.73 \\
\hline
\textbf{Avg. Error} & 4.02\% & \textbf{Std.Dev.} & 2.82\% \\
\hline
\end{tabular}
}
\end{table}
\end{small}

\section{Design Space Exploration Results}\label{results:dse}

Once the high-level synthesis estimations have been validated as fitness function, the design space explorations results are analysed. requirements of a good algorithm to solve the desing space exploration problem are:
\begin{itemize}
\item exploring a wide region the design space;
\item converging to a set of feasible and good solutions, possibly in a quite short time.
\end{itemize}
Figure~\ref{figure:arf_space} and Figure~\ref{figure:chemical_space} show the region explored by an execution of the methodology proposed. Each point in the graph represents a design solution found, with respect to the objectives evaluated (in according to fitness function defined by Eq.~\ref{eq:cost_function}). Figure~\ref{figure:arf_pareto} and Figure~\ref{figure:chemical_pareto} represent the Pareto-optimal solutions (as defined in Definition~\ref{def:pareto_optimal}) found. The figures show that the algorithm is able to explore a large region of the design space and Pareto-optimal solutions cover a good number of solutions between the fastest solution
(with unconstrained number of resources) and the minimal area solution.

\begin{figure}[ht!]
\centering
\includegraphics[width=0.6\columnwidth]{./chapters/experimental_results/images/arf.jpg}
  \caption{Points in the design space explored by the algorithm for the \textit{ARF} benchmark\label{figure:arf_space}}

  \centering
  \includegraphics[width=0.6\columnwidth]{./chapters/experimental_results/images/arf_pareto.jpg}
  \caption{Pareto points generated applying the proposed methodology to the \textit{ARF} benchmark\label{figure:arf_pareto}}
\end{figure}
~
\begin{figure}[ht!]
\centering
\includegraphics[width=0.6\columnwidth]{./chapters/experimental_results/images/chemical.jpg}
  \caption{Points in the design space explored by the algorithm for the\protect \\
 \textit{CHEMICAL} benchmark\label{figure:chemical_space}}

  \centering
  \includegraphics[width=0.6\columnwidth]{./chapters/experimental_results/images/chemical_pareto.jpg}
  \caption{Pareto points generated applying the proposed methodology to the \textit{CHEMICAL} benchmark\label{figure:chemical_pareto}}
\end{figure}
~
\begin{figure}[ht!]
\begin{minipage}[l]{0.5\textwidth}
\centering
\includegraphics[width=0.95\columnwidth]{./chapters/experimental_results/images/dct_space.jpg}
\end{minipage}
~
\begin{minipage}[r]{0.5\textwidth}
  \centering
\includegraphics[width=0.95\columnwidth]{./chapters/experimental_results/images/ewf.jpg}
\end{minipage}
\\
~
\\
~
\\
~
\\
\begin{minipage}[l]{0.5\textwidth}
\centering
\includegraphics[width=0.95\columnwidth]{./chapters/experimental_results/images/pr1.jpg}
\end{minipage}
~
\begin{minipage}[r]{0.5\textwidth}
  \centering
  \includegraphics[width=0.95\columnwidth]{./chapters/experimental_results/images/pr2.jpg}
\end{minipage}
\caption{Regions of the design space explored by the algorithm for a set of benchmarks}\label{fig:regions}
\end{figure}

In Figure~\ref{fig:regions}, different explored regions of the design space have been represented. In all the situations, the methodology is able to explore a large set of alternatives. It is important to notice that the algorithm of sorting and selection do not prefer any of the objectives, so the distribution of explored points with respect the two dimensions (referred as the two objectives) is quite uniform. This is an important feature that it has been obtained thanks to the particular implementation of the NSGA-II algorithm.


\section{Case Study: the JPEG encoder}\label{results:jpeg}

The proposed approach has been used to perform high level synthesis of two steps
of the baseline JPEG compression algorithm with Huffman encoding for a Xilinx 
MicroBlaze System-on-Chip Architecture implemented on a Virtex II-PRO XC2VP4 FPGA device. 

The architecture presents a single MicroBlaze v.5.00.c softcore processor, connected
through a standard On-Chip Peripheral Bus (OPB) to a UART peripheral, an external
memory controller and a SysAce device controller to allow reading and writing of
a Compact Flash memory card. Figure~\ref{fig:jpeg_arch} shows the target architecture.

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.70\columnwidth]{./chapters/experimental_results/images/jpeg_arch.png}
  \caption{Target architecture for the JPEG encoder}\label{fig:jpeg_arch}
\end{figure}

The software application implements the baseline JPEG compression algorithm with Huffman 
encoding and is composed of six phases: (i) original image (.PPM format) reading, 
(ii) RGB to YUV color spaces conversion (for color images), (iii) expansion and downsampling,
(iv) quantization tables setting, (v) bi-dimensional Discrete Cosine 
Transform (2D-DCT), Quantization and zig-zag reordering, (vi) entropic coding and file saving.

It should be noted that the standard JPEG implementation applies
the 2D-DCT on blocks of 64 pixel (8x8).

\begin{small}
\begin{table}
\centering
 \caption{\label{tab:jpegperf} Clock-cycles breakdown of the execution of the JPEG compression algorithm on a single
MicroBlaze architecture with and without the hardware modules synthesized with our evolutionary flow}
\begin{tabular}{|l|r|r|}
\hline
\textbf{Phase} & \textbf{SW} & \textbf{SW/HW}\\
\hline
File reading & 169,512,465 & 171,672,577\\
\textbf{RGB to YUV}   & \textbf{1,598,251,574} & \textbf{1,643,508}\\
Exp \& Downsample  &   678,638 & 679,306\\
Set quant. table   &   60,910 & 61,027\\
\textbf{DCT \& Quant }& \textbf{489,865,154} & \textbf{190,905,503}\\
Entropic coding & 599,810,406 & 592,318,457\\
\hline
\textbf{Total}           & \textbf{2,858,179,147} & \textbf{957,280,378}\\
\hline
\end{tabular}
\end{table}
\end{small}

Table \ref{tab:jpegperf} shows the total execution clock cycles of the JPEG compression algorithm
on a 160x120 pixels image. The most computationally intensive phases are the RGB to YUV conversion
and the 2D-DCT steps. We choose this two parts to be given as input to the proposed high-level synthesis 
flow. A population size of 1.000 individuals was used by the genetic algorithm, evolving up to a maximum of 200 generations. 

The RGB to YUV performs independent elaboration for each pixel of the image, so the loop that applies the conversion
equations to each pixel can be unrolled to parallelize and speed up this phase.

The 2D-DCT, instead, can be decomposed into two mono-dimensional transforms. The software application used, in fact, adopts this decomposition, thus executes a monodimensional DCT on the rows of each 8x8 block and then executes the same monodimensional code working on the columns of the resulting block
from the first transform.

So, before applying the proposed high level synthesis flow to the RGB to YUV conversion routine, it has been unrolled for a factor of four, while the monodimensional DCT routine has been taken without any modifications.

\begin{figure}[t]
  \centering
\includegraphics[width=0.7\columnwidth]{./chapters/experimental_results/images/rgb2yuv.jpg}\label{figure:rgb2yuv}
  \caption{Pareto points generated applying the proposed methodology to the RGB2YUV phase}
\end{figure}

The Xilinx XC2VP4 FPGA is composed of 6,768 logic cells. The base architecture without any accelerators implemented accounts for 2,665 logic elements. The remainings can be used to implement the RGB to YUV and DCT hardware functions. This is, in fact, the area constraints that has been considered to choose the best fit architecture among the solutions obtained with the
evolutionary exploration.

\begin{figure}
  \centering
\includegraphics[width=0.7\columnwidth]{./chapters/experimental_results/images/dct.jpg}\label{figure:dct}
  \caption{Pareto points generated applying the proposed methodology to the DCT phase}
\end{figure}

It is worth noting that the synthesized IP cores have been connected to the MicroBlaze architecture
with a standard Fast Simplex Link (FSL) connection, which offers blocking and non blocking message
passing communication mechanisms. It is also possible, with a minimal overhead in terms of occupation
due to the more complex interface, to adopt also an OPB connection with an interrupt mechanism.

Figure \ref{figure:rgb2yuv} shows the results of our methodology applied on the RGB to YUV conversion routine.
The Pareto points represent the best results in terms of latency for a given area, measured in number
of occupied configurable logic blocks. 

Figure \ref{figure:dct} shows instead the results of the flow applied to the DCT. It is interesting
to note that with 30\% more area the algorithm is able to find a solution three times faster.
The results show that the algorithm is able to explore both the fastest solution
(with unconstrained number of resources) and the minimal area solution, while covering a good number of solutions in between.

Figure \ref{figure:fpga_fit} shows all the possible solutions obtained fully combining all the  
RGB2YUV and DCT Pareto points (see Figures \ref{figure:rgb2yuv} and \ref{figure:dct} respectively) for the 160x120 image.
In Figure \ref{figure:fpga_fit} it is possible to identify the best fitting architecture found by the algorithm for the
target device, which balances the execution latency of both the functions given the remaining
area on the FPGA after the implementation of the base MicroBlaze architecture.

After the synthesis of the hardware accelerators the new JPEG encoder implementation triplicates 
the performance of the baseline software architecture. Performance details about all the phases
of the JPEG algorithm are reported in Table \ref{tab:jpegperf}.

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.7\columnwidth]{./chapters/experimental_results/images/fpga_fit.jpg}
  \caption{Best-fitting architecture for the target XC2VP4 device}\label{figure:fpga_fit}
\end{figure}

%\ \\

\section{Conclusions}
% ######## CONCLUSIONE DEL CAPITOLO.... da sistemare ###############
In this chapter, some experimental results have been presented. Estimations made using the proposed area model and values coming from the real synthesis on FPGA devices are compared, appling the flow to a set of high-level synthesis benchmarks. Results show that the model proposed is good estimator for the real synthesis values. So, using it in the fitness function of the genetic algorithm, the design space exploration has been performed. Explored regions and Pareto-optimal solutions are reported in charts to show the capabilities of the algorithm. At the end a case study is presented: the synthesis of some modules of the JPEG encoder on hardware modules in a FPGA device with strict area constraints. Taking advantage of the proposed methodology, it has been possible to find solutions that allow the design to be implemented on the selected device.